#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

int findElem(vector<int> &input)
{
    int n = input.size();
    for (int i = 0; i < input.size(); i++) {
        if (input[i] <= 0 || input[i] > n) continue;
        while (input[i] != i + 1 && input[input[i]-1] != input[i]) {
            int tmp = input[input[i]-1];
            input[input[i]-1] = input[i];
            input[i] = tmp;
        }
    }

    for (int i = 0; i < input.size(); i++) {
        if (input[i] != i+1) return i+1;
    }

}


int main(int argc, char **argv)
{
    int result;
    
    cout << "----------Test 1 --------" << endl;
    int input[] = {1,2,0};
    vector<int> inputVec;
    for (int i = 0; i < sizeof(input)/sizeof(int); i++)
        inputVec.push_back(input[i]);
    cout << findElem(inputVec) << endl;;

    cout << "----------Test 2 --------" << endl;
    int input2[] = {3,4,-1,1};
    vector<int> inputVec2;
    for (int i = 0; i < sizeof(input2)/sizeof(int); i++)
        inputVec2.push_back(input2[i]);
    cout << findElem(inputVec2) << endl;


    cout << "----------Test 3 --------" << endl;
    int input3[] = {3,4,3,4,2,-1,1};
    vector<int> inputVec3;
    for (int i = 0; i < sizeof(input3)/sizeof(int); i++)
        inputVec3.push_back(input3[i]);
    cout << findElem(inputVec3) << endl;

    cout << "----------Test 4 --------" << endl;
    int input4[] = {-1,-1,-1,1};
    vector<int> inputVec4;
    for (int i = 0; i < sizeof(input4)/sizeof(int); i++)
        inputVec4.push_back(input4[i]);
    cout << findElem(inputVec4) << endl;

    cout << "----------Test 5 --------" << endl;
    int input5[] = {1,1,1,1,1,1,24,24,24};
    vector<int> inputVec5;
    for (int i = 0; i < sizeof(input5)/sizeof(int); i++)
        inputVec5.push_back(input5[i]);
    cout << findElem(inputVec5) << endl;

}
